package com.zhy.algorithm;

import java.util.LinkedList;
import java.util.Queue;
/**
 * @author 随缘而愈
 * @version 1.0
 * @description 广度优先搜索
 * @date 2024/7/15 15:29
 */

public class BfsSearch {
    public static void main(String[] args) {
        // 定义一个图
        int graph[][] = new int[][] {
                {0, 1, 0, 0, 0, 0},
                {1, 0, 1, 1, 1, 0},
                {0, 1, 0, 1, 1, 1},
                {0, 1, 1, 0, 0, 1},
                {0, 1, 1, 0, 0, 1},
                {0, 0, 1, 1, 1, 0}
        };
        // 定义起始顶点
        int startVertex = 0;
        // 广度优先搜索
        bfs(graph, startVertex);
    }

    public static void bfs(int[][] graph, int startVertex) {
        // 获取顶点个数
        int n = graph.length;
        // 定义一个访问标记数组
        boolean[] visited = new boolean[n];
        // 定义一个队列
        Queue<Integer> queue = new LinkedList<>();

        // 将起始顶点标记为已访问
        visited[startVertex] = true;
        // 将起始顶点入队
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            // 取出队列中的第一个元素
            int vertex = queue.poll();
            // 输出该元素
            System.out.println("访问 " + vertex);

            // 遍历该元素的邻接顶点
            for (int i = 0; i < n; i++) {
                // 如果邻接顶点与起始顶点有边且没有被访问过
                if (graph[vertex][i] == 1 && !visited[i]) {
                    // 将该邻接顶点标记为已访问
                    visited[i] = true;
                    // 将该邻接顶点入队
                    queue.add(i);
                }
            }
        }
    }
}
